
/**
 * 
 * 单词接龙
 * 
 * 题目描述

单词接龙的规则是：

可用于接龙的单词首字母必须要前一个单词的尾字母相同
当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词
已经参与接龙的单词不能重复使用
现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，请输出最长的单词串，单词串是单词拼接而成，中间没有空格。

输入描述
输入的：

第一行为一个非负整数，表示起始单词在数组中的索引 K（0 ≤ K < N）
第二行为一个非负整数，表示单词的个数 N
接下来的 N 行，分别表示单词数组中的单词
备注：

单词个数 N 的取值范围为[1, 20]；
单个单词的长度的取值范围为[1, 30]；
输出描述
输出一个字符串，表示最终拼接的单词串。

用例
输入	0
6
word
dd
da
dc
dword
d
输出	worddwordda
说明	先确定起始单词word，再接以d开头的且长度最长的单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出worddwordda。
输入	4
6
word
dd
da
dc
dword
d
输出	dwordda
说明	先确定起始单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出dwordda。
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
  * 
  题目解析
本题我的解题思路如下：

首先，取出第k个单词，作为单词串chain的第一个部分
之后，按照前缀首字母，将剩余单词进行分类，统计为prefix，其中prefix[c]表示c首字母的单词集合
循环如下逻辑：
找到单词串chain的尾字母c，然后找到prefix[c]中最高优先级的单词word，优先级比较如下：

当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词
将word从prefix[c]集合中取出，拼接到chain后面
循环到chain的尾字母c，在prefix中找不到对应单词为止
此时chain即为题解。
  */

public class 单词接龙 {
    public static void main(String[] args) {
        
        try{

            Scanner scanner = new Scanner(System.in);

            //第几个单词为起始接龙
            int startPotion = scanner.nextInt();
            //有几个单词
            int wordCount = scanner.nextInt();
            
            //记录记录接龙列表
            List<String> wordChianList= new ArrayList<>();

            //接受全部word
            List<String> wordList = new ArrayList<>(wordCount);

            for(int i=0; i<wordCount; i++){

                wordList.add(scanner.next());
            }

            //把低 K个直接添加到接龙列表
            wordChianList.add(wordList.remove(startPotion));

            //把剩余的字符串按照首字母封装成一个 map 
            Map<Character, LinkedList<String>> preMap = new HashMap<>();

            for(String word : wordList){

                //首字母
                char c = word.charAt(0);

                preMap.putIfAbsent(c, new LinkedList<>());
                preMap.get(c).add(word);

            }

            //对map里面每个列表进行排序
            for(Character c : preMap.keySet()){

                preMap.get(c).sort((a,b) -> a.length() != b.length() ? b.length() -a.length() : a.compareTo(b));
            }

            while(!preMap.isEmpty()){

                //祛除接龙列表最后一个字符串的最后一个字符
                String chianLlast = wordChianList.get(wordChianList.size()-1);
                char c = chianLlast.charAt(chianLlast.length() - 1);

                //如果 premap 里面没有这个字符，则停止循环
                if(!preMap.containsKey(c) || preMap.get(c).isEmpty()){

                    break;
                }

                wordChianList.add(preMap.get(c).pollFirst());

            }

            System.out.println(String.join("", wordChianList));



        }catch(Exception e){
            e.printStackTrace();
        }
    }
}